/**
 * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
 * <p>
 * 你应当保留两个分区中每个节点的初始相对位置。
 * <p>
 *  
 * <p>
 * 示例:
 * <p>
 * 输入: head = 1->4->3->2->5->2, x = 3
 * 输出: 1->2->2->4->3->5
 */
class Solution {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(4);
        node1.next = node2;
        ListNode node3 = new ListNode(3);
        node2.next = node3;
        ListNode node4 = new ListNode(2);
        node3.next = node4;
        ListNode node5 = new ListNode(5);
        node4.next = node5;
        ListNode node6 = new ListNode(2);
        node5.next = node6;
        ListNode node = partition(node1, 3);
        System.out.println(node);
    }

    /**
     * 双指针法
     *
     * @param head
     * @param x
     * @return
     */
    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        // node记录的是大于x的需要被插入的值
        ListNode node = head;
        ListNode nodePre = null;
        // tmp记录的最新的遍历
        ListNode tmp = null;
        ListNode tmpPre = null;
        boolean finding = false;
        while (node.next != null && (tmpPre == null || tmp != null)) {
            if (finding) {
                if (tmp.val < x) {
                    // 把当前这个小于x的值插入到目标位置之前
                    tmpPre.next = tmp.next;
                    tmp.next = node;
                    if (nodePre == null) {
                        head = tmp;
                    } else {
                        nodePre.next = tmp;
                    }
                    // 互换完成后开始下面的寻找
                    nodePre = tmp;
                    tmp = tmpPre.next;
                } else {
                    // 如果没找到，tmp继续向下走
                    tmpPre = tmp;
                    tmp = tmp.next;
                }
            } else {
                if (node.val >= x) {
                    // 当node大于等于目标值，表示当前节点可以被替换，tmp向下寻找可以替换的值
                    finding = true;
                    if (tmp == null) {
                        tmpPre = nodePre;
                        tmp = node;
                    }
                    tmpPre = tmp;
                    tmp = tmp.next;
                } else {
                    // 无事发生，node向下走
                    nodePre = node;
                    node = node.next;
                }
            }
        }
        return head;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}